CODE 7. Word Ladder

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/12/2013-09-12-CODE 7 Word Ladder/

访问原文「CODE 7. Word Ladder」

Given two words (startandend), and a dictionary, find the length of shortest transformation sequence fromstarttoend, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start="hit"
end="cog"
dict=["hot","dot","dog","lot","log"]
As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length5.
Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

public int ladderLength(String start, String end, HashSet<String> dict) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (start.equals(end)) {
		return 0;
	}
	
	Queue<String> que = new LinkedList<String>();
	que.offer(end);
	dict.add(start);
	int time = 1;
	int layer = que.size();
	while (!que.isEmpty()) {
		String now = que.poll();
		layer--;
		if (now.equals(start)) {
			return time;
		}
		isInDic(dict, now, que);

		if (layer == 0 && !que.isEmpty()) {
			layer = que.size();
			time++;
		}
	}
	return 0;
}

private void isInDic(HashSet<String> dict, String word, Queue<String> que) {
	for (int i = 0; i < word.length(); i++) {
		StringBuilder sb = new StringBuilder(word);
		for (char c = 'a'; c <= 'z'; c++) {
			sb.setCharAt(i, c);
			String t = sb.toString();
			if (dict.contains(t)) {
				dict.remove(t);
				que.offer(t);
			}
		}

	}
}

Konw Something:

1. StringBuilder has a method named setCharAt(int arg0,char arg1).